大企業面試題目古怪　考倒求職者！ - 拼圖

發現到沒有人給賽馬解答，所以來分享一下～








































※ 引述《puzzlez (帕索)》之銘言：
: 「有五個人，五人的年齡都不同，一起走進一家酒吧內圍著一張圓桌子坐下來，他們按年
: 齡大小依次序坐下來的可能性有多大？」

n!/(2n)

: 「二十五匹馬，沒有計時器，有五條賽道。你如何用最少的比賽場數，去找出跑得最快的
: 三匹馬？」（facebook面試題目）

最佳解 7.

總共有 25 匹馬，每次比較最多只能多知道 4 個最簡大小關係（我自己亂發明的詞）。例如
第一場是 a,b,c,d,e 就知道 e > d > c > b > a. 可以畫成一個 directed acyclic graph.
至少要知道 24 個最簡大小關係（因為連通圖至少要 n-1 邊）所以至少要 6 場。假如 6 場
可以，最後一場一定是 5 個完全獨立的組各派代表出來，必然有一種結果會無法選出前三，
所以至少要 7 場。

: 「你爬樓梯，每次走一級或兩級，那道樓梯有n那麼多級，你有甚麼與別不同的方法去爬
: ？」（Google）

fib n = theta (phi^n)

--